#!/usr/bin/python
import random

class SkipList(object):
    class Node(object):
        def __init__(self, key=None, val=None, level=0):
            self.__level = level
            self.__key = key
            self.__value = val
            self.__nexts = []

        @property
        def level(self):
            return self.__level
        @level.setter
        def level(self, val):
            self.__level = val

        @property
        def key(self):
            return self.__key
        @key.setter
        def key(self, val):
            self.__key = val

        @property
        def value(self):
            return self.__value
        @value.setter
        def value(self, val):
            self.__value = val

        @property
        def nexts(self):
            return self.__nexts
        @nexts.setter
        def nexts(self, val):
            self.__nexts = val

        def __str__(self):
            #return "l:%s,k:[%s],v:%s,n:%s" % (self.__level, self.__key, self.__value, self.__nexts)
            #return "l:%s,k:[%s],v:%s,n:%d" % (self.__level, self.__key, self.__value, len(self.__nexts))
            return "k:[%s],v:%s" % (self.__key, self.__value)
        

    def __str__(self):
        ret = "SkipList:\n"
        for i in range(0, self.__maxLevel):
            cur = self.__head
            while len(cur.nexts) > 0:
                ret += str(cur) + "  "
                cur = cur.nexts[i]
            ret += str(cur) + "\n"
        return ret

    def __init__(self, maxLevel):
        self.__maxLevel = maxLevel > 0 and maxLevel or 1
        self.__head = SkipList.Node("H")
        self.__tail = SkipList.Node("T")

        self.__size = 0
        
        for i in range(0, self.__maxLevel):
            self.__head.nexts.append(self.__tail)


    def size(self):
        return self.__size

    def getLevel(self):
        level = 0
        while random.randint(0, 1024*64-1) % 2 != 0 and level < self.__maxLevel -1:
            level += 1
        return level > 0 and level or 1
        #return 10

    def get(self, key):
        cur = self.__head
        for i in range(self.__maxLevel - 1, -1, -1):
            while cur.nexts[i] != self.__tail:
                curKey = cur.nexts[i].key
                if key > curKey:
                    cur = cur.nexts[i]
                elif key == curKey:
                    return cur.nexts[i].value
                else:
                    break;
            #end while
        return None
    #end def

    # ret : 1 -> replaced;  0 -> insert 
    def put(self, key, val):
        level = self.getLevel()
        #print("level:[" + str(level) + "]   key:%s" % (key))

        cur = self.__head
        prevs = [ None for i in range(level)]
        for i in range(level-1, -1, -1):
            #print(".....i....." + str(i) + "cur:" + str(cur))
            while cur.nexts[i] != self.__tail:
                curKey = cur.nexts[i].key
                if key > curKey:
                    cur = cur.nexts[i]
                elif key == curKey:
                    cur.nexts[i].value = val
                    return 1
                else:
                    break
            #end while
            prevs[i] = cur
        #end for

        node = SkipList.Node(key, val, level)

        for i in range(0, level):
            node.nexts.append(prevs[i].nexts[i])
            prevs[i].nexts[i] = node

        self.__size += 1
        return 0

    def delete(self, key):
        cur = self.__head
        prevs = [None for i in range(self.__maxLevel)]
        for i in range(self.__maxLevel-1, -1 , -1):
            while cur.nexts[i] != self.__tail:
                curKey = cur.nexts[i].key
                if key > curKey:
                    cur = cur.nexts[i]
                    continue
                elif key == curKey:
                    prevs[i] = cur
                    break
                else:
                    break
            #end while
        #end for
        node = None
        for i in range(0, self.__maxLevel):
            if prevs[i] is not None:
                node = prevs[i].nexts[i]
                prevs[i].nexts[i] = node.nexts[i]
        self.__size -= 1
        return node

    def clean(self):
        while self.__head.nexts[0] != self.__tail:
            node = cur.nexts[0]
            self.__head.nexts[0] = node.nexts[0]
            node = None
        self.__head = None
        self.__tail = None
        self.__size = 0

    def first(self):
        return self.__head.nexts[0]
    def last(self):
        return self.__tail

    class Iterator(object):
        def __init__(self, skipList):
            self.__skipList = skipList
            self.__cur = self.__skipList.first()

        def hasNext(self):
            return self.__cur != self.__skipList.last()

        def next(self):
            cur = self.__cur
            self.__cur = self.__cur.nexts[0]
            return (cur.key, cur.value)

    def iterator(self):
        return SkipList.Iterator(self)

import unittest
class TestSkipList(unittest.TestCase):
    def testNode(self):
        n = SkipList.Node() 
        n.level = 1
        n.key = 1
        n.value = "hello"
        n.nexts.append(1)
        print(str(n))

    def testSkipList(self):
        sl = SkipList(10)

        #put ......
        def insert(sl, key, val):
            sl.put(key, val)
            print(str(key) + " " + str(sl))
            
        for i in range(1, 9):
            insert(sl, i, "hello")
        insert(sl, 8, "hello8")
        self.assertEqual(8, sl.size())
        

        #get ....
        def get(sl, key):
            val = sl.get(key)
            print(val is None and ("key:%s->None" % key)  or ("key:%s->%s"% (key, val)))
            return val
        for i in range(1, 9):
            self.assertIsNotNone(get(sl, i))
        self.assertIsNone(get(sl, 0))
        self.assertIsNone(get(sl, 10))

        it = sl.iterator()
        while it.hasNext():
            print( "iterator: " +  str(it.next()))

        #delete ...... 
        def delete(sl, key):
            val = sl.delete(key)
            #print( val is None and ("can not find key:[%s]" % key) or ("delete:[%s] ok" % key) )
            return val
        for i in range(1, 9):
            self.assertIsNotNone(delete(sl, i))

        self.assertEqual(0, sl.size())

        self.assertIsNone(delete(sl, 0))
        self.assertIsNone(delete(sl, 10))



        #clean resource
        sl.clean()

    def testEmptySkipList(self):
        sl = SkipList(10)
        self.assertIsNone(sl.get(0))
        self.assertIsNone(sl.delete(0))
        sl.clean


if __name__ == "__main__":
    suite = unittest.TestSuite([
        unittest.TestLoader().loadTestsFromTestCase(TestSkipList), 
    ])
    unittest.TextTestRunner(verbosity=2).run(suite)
